// @algorithm @lc id=100318 lang=cpp
// @title shu-zu-zhong-de-ni-xu-dui-lcof

#include "algm/algm.h"
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class Solution {
    // @test([7,5,6,4])=5
public:
    int reversePairs(vector<int> &nums) {
        int n = nums.size();
        vector<int> tmp(n);
        return mergeSort(nums, tmp, 0, n - 1);
    }
    // 归并排序
    int mergeSort(vector<int> &nums, vector<int> &tmp, int l, int r) {
        // 当剩下单元素数组时，一定为有序数组
        if (l >= r) {
            return 0;
        }
        // 找到分界中点
        int mid = (l + r) / 2;
        // 继续分治
        int inv_count = mergeSort(nums, tmp, l, mid) + mergeSort(nums, tmp, mid + 1, r);
        // i和j是左右数组的指针，tmp为构造出的新的数组
        int i = l, j = mid + 1, pos = l;
        while (i <= mid && j <= r) {
            if (nums[i] <= nums[j]) {
                tmp[pos] = nums[i];
                ++i;
                // j-(mid+1)是右边数组中减少的元素个数，这部分元素比nums[i]小，却在nums[i]右边，所以就是逆序数对
                inv_count += (j - (mid + 1));
            }
            else {
                tmp[pos] = nums[j];
                ++j;
            }
            ++pos;
        }
        // 左边还剩下的有
        for (int k = i; k <= mid; ++k) {
            tmp[pos++] = nums[k];
            inv_count += (j - (mid + 1));
        }
        // 右边还剩下的有
        for (int k = j; k <= r; ++k) {
            tmp[pos++] = nums[k];
        }
        copy(tmp.begin() + l, tmp.begin() + r + 1, nums.begin() + l);
        return inv_count;
    }
};